/**
 * 堆排序
 */
;(function(window){
	window.HeapSort = {
		_insertAt: function(idx, data){
			this._heapArr[idx] = data;
			this._length++;
		},
		_deleteNode: function(){
			var rootNode = this._heapArr[0];
			this._heapArr[0] = this._heapArr[--this._length];
			this._trickleDown(0);
			delete this._heapArr[this._length]; // 必须把数组的最后一个元素清除
			return rootNode;
		},
		_trickleDown: function(idx){
			var largerIdx;
			var topNode = this._heapArr[idx];
			while(idx < Math.floor(this._length/2)){
				var lIdx = 2*idx+1;
				var rIdx = lIdx+1;
				if(rIdx < this._length && this._heapArr[lIdx] < this._heapArr[rIdx]){
					largerIdx = rIdx;
				}else{
					largerIdx = lIdx;
				}
				if(topNode >= this._heapArr[largerIdx]){
					break;
				}
				this._heapArr[idx] = this._heapArr[largerIdx];
				idx = largerIdx;
			}
			this._heapArr[idx] = topNode;
		},
		sort: function(datas){
			this._heapArr = [];
			this._length = 0;
			var ln = datas.length;
			for( var i=0;i<ln; i++)
				this._insertAt(i, datas[i]);

			for(var j=Math.floor(ln/2)-1; j>=0; j--)
				this._trickleDown(j);

			for( i=0; i<ln; i++)
				datas[i] = this._deleteNode();
		}
	};
})(window);